#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

void PrintArray(int* a, int n)
{
	int i = 0;
	for ( i = 0; i < n; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int  GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[left] > a[right])
		{
			return  left;
		}
		else if ( a[right] > a[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
 }
int Part1(int* a, int left, int right)
{

	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi], &a[left]);
	}

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);
	keyi = left;
	return keyi;

}

int QuickSortPart3(int* a, int left, int right) {
	
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi], &a[left]);
	}

	int keyi = left;

	int slow = left;
	int fast = left + 1;
	while (fast <= right)
	{
		if(a[fast] < a[keyi] && ++slow!= fast)
		{
			Swap(&a[fast], &a[slow]);

		}
		fast++;
	}

	Swap(&a[slow], &a[keyi]);
	keyi = slow;
	return keyi;

}


void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = Part1(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}
int main()
{
	int a[10] = { 0,2,4,5,1,3,7,9,8,6 };

   /* InsertSort(a, 10);
	PrintArray(a, 10);
	*/

	//ShellSort(a, 10);
	//PrintArray(a, 10);

	//SSelectSort(a, 10);
	//PrintArray(a, 10);

	//HeapSort(a, 10);
	//PrintArray(a, 10);

	//BubbleSort(a, 10);
	//PrintArray(a, 10);

	 QuickSort(a,0,10);
	 PrintArray(a,10);

	//MergeSort(a,10);
	//PrintArray(a,10);


	return 0;
}

